BZOJ1913【APIO2010】信号覆盖 <极角排序+双指针>

Problem

【APIO2010】信号覆盖

Description

Input

输入第一行包含一个正整数，表示房子的总数。接下来有行，分别表示每一个房子的位置。对于，第个房子的坐标用一对整数和来表示，中间用空格隔开。

Output

输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，需保证输出结果与精确值的绝对误差不超过。

Sample Input

Sample Output

3.500

HINT

的数据，
的数据，
的数据，
的数据保证，对于，第个房子的坐标为整数且。
任何三个房子不在同一条直线上，任何四个房子不在同一个圆上。

标签：极角排序 双指针

Solution

总体思路是求出所有三元组形成的圆能多覆盖的点的总数，

对于任意四点构成的四边形，考虑任选其中任意三点形成的圆能否包括另一个点。
有两种情况：

凹四边形：除凹进去的点外另外三点的外接圆可以包括凹进去的点外，其余三元组构成的圆一定不能包括第四点，故贡献为。
凸四边形：由于不存在共圆四边形，对角和一定一个大于，一个小于。只有对角和大于的两个角上三点的外接圆能包括另一点，故贡献为。

因此。

接下来考虑如何求两种四边形的个数。由于，我们只用求凹四边形个数即可。
枚举每个点，考虑其作为凹四边形凹进去的那个点又多少种情况。易知。于是需要求含此点的凸多边形数。即枚举凸多边形上的另一个点，看有多少点使得和的夹角小于。这个过程可以用极角排序后双指针扫一遍统计。这样计算出凹多边形数后即可得到最终答案。

Code

#include <bits/stdc++.h>
#define Pi acos(-1)
#define x first
#define y second
#define MAX_N 1500
using namespace std;
typedef double dnt;
typedef long long lnt;
typedef pair<dnt,dnt> pdd;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; lnt c1, c2; pdd p[MAX_N+5];
lnt C(int n, int m) {
    lnt ret = 1LL;	if (n < m) return 0LL;
    for (int i = 1; i <= m; i++) ret *= 1LL*(n-i+1);
    for (int i = 1; i <= m; i++) ret /= i;
    return ret;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++)
        read(p[i].x), read(p[i].y);
    for (int i = 1, m = 0; i <= n; i++, m = 0) {
        lnt tot = 0LL; dnt a[MAX_N*2+5];
        for (int j = 1; j <= n; j++) if (i^j)
            a[++m] = atan2(p[j].y-p[i].y, p[j].x-p[i].x);
        for (int j = 1; j <= n; j++) if (a[j] < 0) a[j] += 2*Pi;
        sort(a+1, a+m+1);
        for (int j = 1; j <= m; j++) a[m+j] = a[j]+2*Pi;
        for (int u = 1, v = 1; u <= m; tot += C(v-u, 2), u++)
            while (v < (m<<1) && a[v+1]-a[u] < Pi) v++;
        c1 += C(m, 3)-tot;
    }
    c2 = C(n, 4)-c1;
    return printf("%.6lf\n", (dnt)(c1+c2*2)/(dnt)C(n, 3)+3), 0;
}